\begin{abstract}

Best-first search is one of the most fundamental techniques 
for planning. A heuristic function is used in best-first search 
to guide the search. A well-observed 
phenomenon on best-first search for planning 
is that for most of the time during search, 
it explores a large number of states without 
reducing the heuristic function value. 
This phenomenon, called ``plateau exploration'', has been 
extensively studied for heuristic 
search algorithms for satisfiability (SAT) and constraint satisfaction problems (CSP).

In planning, plateau exploration consists of most of the search time
in state-of-the-art best-first search planners. Therefore, 
their performance can be improved
if we can reduce the plateau exploration time by finding 
an exit state (a state with better heuristic value than 
the best one found so far) of that plateau. In this paper, we propose a random-walk assisted best-first search algorithm for planning which invokes a random walk procedure to find exits when
the best-first search is stuck on a plateau. 

We establish a theoretical model to analyze the conditions when
a random walk is helpful to best-first search in finding plateau exits. 
We subsequently implement two variants of the proposed scheme, 
including a sequential version and a parallel one, to compare their performances 
with LAMA, the baseline best-first search planner. 
Our experimental results not only show the advantages of using 
random-walk to assist best-first search for planning problems, but also 
validates the performance analysis in the theoretical model. 

\end{abstract}

%  of both best-first search and random walk algorithms in finding exits.